// 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

function longestValidParentheses(s: string): number {
    const stack: Array<number> = [];// 栈
    let maxLen: number = 0;// 子串最长长度
    stack.push(-1);// 初始化栈顶元素为-1，表示下一个入栈的子串开头索引大于-1
    for (let i = 0; i < s.length; i++) {
        // 将所有的左括号索引入栈
        if (s[i] === "(") {
            stack.push(i);
        } else {// 扫描右括号，记得先出栈当前元素
            stack.pop();
            if (stack.length === 0) {// 栈为空时右括号索引入栈，实现记忆化
                stack.push(i);
            } else {// 栈不为空时计算当前的子串长度，更新maxLen变量
                let currLen = i - stack[stack.length - 1];
                maxLen = Math.max(maxLen, currLen);
            }
        }
    }
    return maxLen;
};

// 这道题目是一个比较典型的括号对的问题，我们可以使用单调栈求解
// 但讨论具体情况较为困难也不好想（爱考难的算法题是字节跳动传统艺能）
// 我们将所有的左括号存入栈中，右括号不入栈
// 然后等待一个右括号来和栈中的左括号进行匹配
// 匹配成功时，就弹出栈中的左括号然后相当于当前的子串长度+2
// 值得注意的是因为我们只需要计算子串的长度而不是具体的子串，所以只需要存入左括号的索引
// 当左右括号相遇时，我们可以用当前的左括号与右括号的索引差进行子串长度的计算
// 例如当遇到（（（））时，最后一个右括号索引为4，可以消去栈中索引为1的左括号
// 但这种单纯的思考逻辑会遇到一个问题，例如说当遇到（）（（）））时，显然此时的最长子串长度应该为0~5 = 6
// 但是因为这种括号的组合形式刚好能消掉，栈不具备记忆性，所以此时右括号消去时我们只能统计出4而算不出6
// 我们考虑提前给栈中赋一个初值-1，让栈具备记忆性，表示下一个入栈的子串开头索引大于-1（因为字符串开头索引是0）
// 这样当我们计算括号消去的时候，只需要先把当前元素出栈，然后计算栈顶元素与当前元素索引的差值；
// 例如（）扫描到）时，左括号出栈，栈中剩下的元素是-1，只需要1-（-1）= 2，即可计算出当前子串长度为2
// 而回到刚刚的（）（（））），当索引为5的右括号入栈，会遇到栈顶元素-1，然后5减去-1 = 6，就可以计算出当前的子串长度
// 然后扫描到索引为6的右括号时，因为栈为空，所以把6入栈，表示下一个入栈的子串开头索引大于6
// 这样就让这个单调栈拥有了记忆性，同时解决了子串长度计算的问题。

